package com.leetcode.根据算法进行分类.前缀和相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/2
 * @description: 304. 二维区域和检索 - 矩阵不可变
 * https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
 */
public class B_304_二维区域和检索_矩阵不可变 {


	public static void main(String[] args) {
		test1();
	}


	public static void test1() {
		// 3
		int[][] matrix = new int[][]{
				{3, 0, 1, 4, 2},
				{5, 6, 3, 2, 1},
				{1, 2, 0, 1, 5},
				{4, 1, 0, 1, 7},
				{1, 0, 3, 0, 5}
		};
		NumMatrix numMatrix = new NumMatrix(matrix);
		System.out.println(numMatrix.sumRegion(2, 1, 4, 3));
		System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
		System.out.println(numMatrix.sumRegion(1, 2, 2, 4));
	}


	/**
	 * 这道题近似 {@link A_303_区域和检索_数组不可变 }
	 * sumRegion(row1, col1, row2, col2) = sumRegion(0, 0, row2, col2) + sumRegion(0, 0, row1-1, col1-1)
	 * - sumRegion(0, 0, row1-1, col2) - sumRegion(0, 0, row2, col1-1)
	 */
	static class NumMatrix {

		int[][] prefixSum;

		/**
		 * 计算前缀和进行保存
		 * 前缀和的计算也需要讨巧一下：
		 * sumRegion(0, 0, row, col) = sumRegion(0, 0, row-1, col) + sumRegion(0, 0, row, col-1)
		 * - sumRegion(0, 0, row-1, col-1) + matrix[row][col]
		 *
		 * @param matrix
		 */
		public NumMatrix(int[][] matrix) {
			if (matrix == null) {
				return;
			}
			//行
			int m = matrix.length;
			if (m == 0) {
				return;
			}
			//列
			int n = matrix[0].length;
			if (n == 0) {
				return;
			}
			prefixSum = new int[m][n];
			//求前缀和，区分讨论
			//TODO:如果新建的是 m 行 n 列的二维数组，就可以避免对头行/头列 元素进行额外的判断
			//1.(0,0) 处的值
			prefixSum[0][0] = matrix[0][0];
			//2.第一行的值
			for (int i = 1; i < n; i++) {
				prefixSum[0][i] = prefixSum[0][i - 1] + matrix[0][i];
			}
			//3.第一列的值
			for (int i = 1; i < m; i++) {
				prefixSum[i][0] = prefixSum[i - 1][0] + matrix[i][0];
			}
			//4.第二行/列 开始遍历求解
			for (int i = 1; i < m; i++) {
				for (int j = 1; j < n; j++) {
					prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
							+ matrix[i][j];
				}
			}
		}

		public int sumRegion(int row1, int col1, int row2, int col2) {
			if (row1 == 0 && col1 == 0) {
				return prefixSum[row2][col2];
			}
			if (row1 == 0) {
				return prefixSum[row2][col2] - prefixSum[row2][col1 - 1];
			} else if (col1 == 0) {
				return prefixSum[row2][col2] - prefixSum[row1 - 1][col2];
			}

			return prefixSum[row2][col2] + prefixSum[row1 - 1][col1 - 1] -
					prefixSum[row1 - 1][col2] - prefixSum[row2][col1 - 1];
		}
	}
}
